#include <iostream>
#include <ctime>
#include <assert.h>

using namespace std;

template<typename T>
int binarySearch(T arr[], int n, T target) {
    int l=0,r=n-1;
    while (l <= r) {
        int mid=l+(r-l)/2;
        if (arr[mid]==target)
            return mid;
        else if(arr[mid]>target)
            r=mid-1;
        else
            l=mid+1;
    }
    return -1;
}
template<typename T>
int __binarySearch2(T arr[], int l,int r, T target) {
    if( l > r )
        return -1;
    int mid=l+(r-l)/2;
    if(target==arr[mid])
        return mid;
    else if(arr[mid]>target)
        return __binarySearch2(arr,l,mid-1,target);
    else
        return __binarySearch2(arr,mid+1,r,target);
//    return -1;
}
template<typename T>
int binarySearch2(T arr[], int n,T target){
    __binarySearch2(arr,0,n-1,target);
}
int main() {
    int n = 1000000;
    int* a = new int[n];
    for( int i = 0 ; i < n ; i ++ )
        a[i] = i;
    clock_t startTime = clock();
    for( int i = 0 ; i < 2*n ; i ++ ){
        int v = binarySearch(a, n, i);
        if( i < n )
            assert( v == i );
        else
            assert( v == -1 );
    }
    clock_t endTime = clock();
    cout << "Binary Search (Without Recursion): " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;

    startTime = clock();
    for( int i = 0 ; i < 2*n ; i ++ ){
        int v = binarySearch2(a, n, i);
        if( i < n )
            assert( v == i );
        else
            assert( v == -1 );
    }
    endTime = clock();
    cout << "Binary Search (Recursion): " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;
    delete[] a;
    return 0;
}